package com.zzz.offer.twoarraysearch;

public class ArraySearch {
    public static void main(String[] args) {
        int[][] array = {{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}};
//        int[][] array = {{1, 1}};
        System.out.println(new Solution().Find(0, array));
    }
}

class Solution {

    // 我脑子有问题，想到从横向 再纵向
    public boolean Find(int target, int[][] array) {

        if (array[0].length == 0) {
            return false;
        }

        /*
            从 i=0 j=0  开始横向遍历 到头了开始纵向遍历
            拿 element = array[i][j]
            如果element > target  那么 >i > j 的范围内的数据都无效
            如果element < target  那么 <i  <j 的范围内的数据都无效

         */
        int minU = 0;
        int maxR = array[0].length - 1;

        while (minU <= array.length - 1 && maxR >= 0) {

            // 横向遍历
            for (int j = 0; j <= maxR; j++) {
                if (array[minU][j] == target) {
                    return true;
                } else if (array[minU][j] > target) {
                    // 发现有个元素大于目标，说明该元素右边包括本身全部大于目标，因为从第一行遍历，所以不存在
                    // 右上角等于目标值的情况，要么都小于，要么都大于
                    maxR = j - 1;
                    break;
                }
            }
            // 如果第一列就大于目标值，说明不存在 目标相等的元素
            if (maxR < 0) {
                return false;
            }

            minU += 1;

            // 纵向遍历  如果找到大于目标值，那和上面一样，排除了该列及右边的元素
            for (int i = minU; i <= array.length - 1; i++) {
                if (array[i][maxR] == target) {
                    return true;
                } else if (array[i][maxR] > target) {
                    // 找到了大于目标值的元素，右边的边界可以减一了
                    // 相当于这个元素左上上都是小于目标值，
                    // 下次遍历直接在本行 开头遍历这行
                    minU = i;
                    maxR -= 1;
                    break;
                }
            }
        }
        return false;
    }

    // 从右上角开始遍历  这才是 N + M 的方式
    public boolean Find1(int target, int[][] array) {

        int row = 0;
        int col = array[0].length - 1;
        while (row <= array.length - 1 && col >= 0) {
            if (target == array[row][col])
                return true;
            else if (target > array[row][col])
                row++;
            else
                col--;
        }
        return false;
    }

}
